package com.gl.marina;
public class BinaryTree <T extends Comparable<T>> {
    class Node<T extends Comparable<T>>{
        private Node <T> root;
        public Node <T>rightChild;
        public Node <T>leftChild;
        public T data;
        private Node <T>node;
        public Node(T data){
            rightChild=null;
            leftChild=null;
            this.data=data;
        }
        public boolean addNode(T data){
             root = addNode(root, data);
             return true;
             }
        private  Node addNode(Node node,T data){
            if(node==null){
                node=new Node<T>(data);
            }else
            if(node.data.compareTo(data)<=0){
                node.rightChild = addNode(node.rightChild, data);
            }else
                node.leftChild=addNode(node.leftChild, data);
            return(node);
        }
        public boolean lookingFor(T data){
            return (lookingFor(root, data));
        }
        public boolean lookingFor(Node node,T data){
            if (node==null) {
                return(false);
            }else
            if (data==node.data) {
                return(true);
            }else
            if(node.data.compareTo(data)<=0){
                return lookingFor(node.rightChild,data);
            }else
                return lookingFor(node.leftChild,data);
        }
        public int size(){
            return (size (root));
        }
        private int size(Node node){
            if(node==null){return 0;
            }else
                return (size(node.leftChild)+1+size(node.rightChild));
        }
       public void remove(T data){
           root = remove(root,data);
       }
        protected Node remove(Node<T> node,T data) {
            if (node == null) {
                return null;
            }
            if (data.compareTo(node.data) == 0) {
               if (node.leftChild == null) {
                   return node.rightChild;
               } else
               if (node.rightChild == null) {
                   return node.leftChild;
               } else {
                   node.data = replace(node.leftChild);
                   node.leftChild = remove( node.leftChild,node.data);
               }
               } else{
                if (data.compareTo(node.data) < 0) {
                   node.leftChild = remove(node.leftChild,data);
               } else{
                   node.rightChild = remove(node.rightChild,data);

               }
           }
            return node;
       }
       protected T replace(Node<T> node) throws NullPointerException{
           if(node==null){throw new NullPointerException(); }
          Node right = node.rightChild;
           if (right == null) {
               return (T) node.data;
           } else {
               return replace(right);
           }
        }
       public Node<T> removeAll(){
           return removeAll(root);
       }
       private Node<T> removeAll(Node node){
           if(root!=null){
               root=null;
               return removeAll();}
           else
           return null;  }
       public void printGoDown(int depth){
           for (int i = 1; i <= depth; i++) {
               System.out.print(printGoDown(root, i) + "\n");
           }
       }

       public String printGoDown(Node node, int level) {
           if (node == null) {
               return " ";
           }if (level == 1) {
               return " "+ node.data + " ";
           }else if (level > 1) {
               String leftVal = printGoDown(node.leftChild, level - 1);
               String rightVal = printGoDown(node.rightChild, level - 1);
               return leftVal+rightVal;
           }else
               return "";
       }

       public void printGoRight(int level){
        printGoRight(root,level);
    }
        private  void printGoRight(Node node, int level){
            if(node==null)
                return;
            printGoRight(node.rightChild, level + 1);
            if(level!=0){
                for(int i=0;i<level-1;i++)
                    System.out.print("\t");
                System.out.println(" "+node.data);
            }else
                System.out.println(node.data);
            printGoRight(node.leftChild, level + 1);
        }
    }
}
